public class Solution148 {
    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    private int getLen(ListNode node){
        for (int len = 0; ; node = node.next, len++) {
            if(node == null){
                return len;
            }
        }
    }

    private ListNode getDistanceNode(ListNode node, int step){
        for (int i = 0; i < step; i++) {
            if(node == null){return null;}
            node = node.next;
        }
        return node;
    }

    private ListNode[] mergeSortNode(ListNode node1, ListNode node2, int step){
        ListNode newHead = new ListNode(-1), tailNode = newHead;
        int step1 = 1, step2 = 1;
        while(step1 <= step && step2 <= step &&
            node1 != null && node2 != null){
            if(node1.val < node2.val){
                tailNode.next = node1;
                tailNode = tailNode.next;
                node1 = node1.next;
                step1++;
            }
            else{
                tailNode.next = node2;
                tailNode = tailNode.next;
                node2 = node2.next;
                step2++;
            }
        }
        for (; step1 <= step && node1 != null;
            tailNode.next = node1,
            tailNode = tailNode.next,
            node1 = node1.next,
            step1++){}
        for (; step2 <= step && node2 != null;
             tailNode.next = node2,
            tailNode = tailNode.next,
            node2 = node2.next,
            step2++){}
        tailNode.next = null;
        return new ListNode[]{newHead.next, tailNode};
    }

    public ListNode sortList(ListNode head) {
        ListNode tmpHead = head;
        int len = getLen(head);
        for (int i = 1; i < len; i *= 2) {
            ListNode newHead = new ListNode(-1), tailNode = newHead, tmpNode = tmpHead;
            while(tmpNode != null){
                ListNode distanceNode = getDistanceNode(tmpNode, i), doubleDistanceNode = getDistanceNode(distanceNode, i);
                ListNode[] headAndTail = mergeSortNode(tmpNode, distanceNode, i);
                tailNode.next = headAndTail[0];
                tailNode = headAndTail[1];
                tmpNode = doubleDistanceNode;
            }
            tmpHead = newHead.next;
        }
        return tmpHead;
    }

    private ListNode buildNodeList(int[] valList){
        ListNode head = new ListNode(-1), tail = head;
        for (int val : valList) {
            tail.next = new ListNode(val);
            tail = tail.next;
        }
        return head.next;
    }
    public static void main(String[] args) {

        Solution148 s = new Solution148();
        s.sortList(s.buildNodeList(new int[]{4,2,1,3}));
    }
}
